//#include "../../dxhead/dxegheader.h"
#include "../inc/skyMath.h"
#include "../inc/skyTrace.h"
namespace Sky
{
i32 NMath::x_exgcd_divide( i32 a, i32 b, i32* x, i32* y )
{
	if(b == 0){*x = 1;*y = 0;return a;}
	i32 r = x_exgcd_divide(b, a % b, x, y);
	i32 t = *x;
	*x = *y;
	*y = t - a / b *(*y);
	return r;
}

i32 NMath::x_gcd_iterator( i32 a,i32 b )
{ 
	i32 r=a%b;
	while(r){a=b;b=r;r=a%b;}
	return b;
}

i32 NMath::x_exgcd_iterator( i32 a,i32 b,i32* x,i32* y )
{
	i32 xi,yi,xi_1,yi_1;
	i32 r,q=0;
	*x=0;*y=1;
	xi_1=1;yi_1=0;
	xi=0;yi=1;
	r=a%b;//r=x_mode(a,b);

	while(r)
	{
		q=(a-r)/b;
		*x=xi_1-q*xi;
		*y=yi_1-q*yi;
		xi_1=xi;yi_1=yi;
		xi=*x;yi=*y;

		a=b,b=r;r=a%b;
	}
	return b;
}

i32 NMath::x_gcd_minus( i32 a,i32 b )
{
	while(1)
	{
		if(a>b) a-=b;
		else if(a<b)b-=a;
		else return a;
	}
}

i32 NMath::x_gcd_effect1( i32 a,i32 b )
{
	while(1)
	{
		a%=b;
		if(a==0)return b;
		if(a==1)return 1;
		b%=a;
		if(b==0)return a;
		if(b==1)return 1;
	}
}

i32 NMath::x_gcd_effect2( i32 a,i32 b )
{
	while(1)
	{
		if(a>(b*4))
		{
			a%=b;
			if(a==0)return b;
			if(a==1)return 1;
		}
		else if(a>=b)
		{
			a-=b;
			if(a==0)return b;
			if(a==1)return 1;
		}
		if(b>(a*4))
		{
			b%=a;
			if(b==0)return a;
			if(b==1)return 1;
		}
		else if(b>=a)
		{
			b=b-a;
			if(b==0)return a;
			if(b==1)return 1;
		}
	}
}

i32 NMath::x_gcd_stein( i32 a, i32 b )
{
	if(a == 0) return b;
	if(b == 0) return a;
	if(a % 2 == 0 && b % 2 == 0) return 2 * x_gcd_iterator(a >> 1, b >> 1);
	else if(a % 2 == 0)  return x_gcd_iterator(a >> 1, b);
	else if(b % 2 == 0) return x_gcd_iterator(a, b >> 1);
	else return x_gcd_iterator((a - b) > 0 ? a-b : b-a, a>b?b:a);
}
}
